#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* head;
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* node_pre = NULL;
        ListNode* head_bak = head;
        ListNode* buff[n] = {NULL}; // = new ListNode(0);
        int index = 0;
        while(head){
            if (index >= n){
                node_pre = buff[index % n];
            }
            buff[index % n] = head;
            index++;
            head = head->next;
        }
        if (node_pre){// delete mid node
            node_pre->next = buff[index % n]->next;
            delete buff[index % n];
            return head_bak;
        }else{ //delete first node
            ListNode* temp;
            temp = head_bak;
            head_bak = head_bak->next;
            delete temp;
            return head_bak;
        }
//        standard answer
//        ListNode *pre=head,*cur=head;
//        for(int i=0;i<n;i++)cur=cur->next;
//        if(!cur)return head->next;
//        while(cur->next){
//            pre=pre->next;
//            cur=cur->next;
//        }
//        pre->next=pre->next->next;
//        return head;

    }
};

ListNode* createList(int num, uint32_t max)
{
    ListNode* head;
    ListNode* node;
    if (0 == num) return NULL;
    srand(clock());
    head = new ListNode(rand()%max);
    node = head;
    for (int i = 0; i < num-1; i++){
        node->next = new ListNode(rand()%max);
        node = node->next;
    }
    return head;
}

void printList(ListNode* node)
{
    int cnt = 0;
    cout << "node print start:" << endl;
    while(node){
        cout << ++cnt << ":" << node->val << endl;
        node = node->next;
    }
    cout << "node print end" << endl;
}

int main(void)
{
    Solution su;
    su.head = createList(1, 100);
    printList(su.head);
    ListNode* list = su.removeNthFromEnd(su.head, 1);
    printList(list);
    return 0;
}
